package demo1;

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val) {
        this.val = val;
    }
}

public class BinaryTree {
    public int count;
    public TreeNode createBinaryTree() {
        TreeNode treeNode1 = new TreeNode('A');
        TreeNode treeNode2 = new TreeNode('B');
        TreeNode treeNode3 = new TreeNode('D');
        TreeNode treeNode4 = new TreeNode('E');
        TreeNode treeNode5 = new TreeNode('H');
        TreeNode treeNode6 = new TreeNode('C');
        TreeNode treeNode7 = new TreeNode('F');
        TreeNode treeNode8 = new TreeNode('G');
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode6;
        treeNode2.left = treeNode3;
        treeNode2.right = treeNode4;
       // treeNode4.right = treeNode5;
        treeNode6.left = treeNode7;
        treeNode6.right = treeNode8;
        return treeNode1;
    }

    //前序遍历
    /*public void preOrder (BTNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        count++;
        preOrder(root.left);
        preOrder(root.right);
    }*/
    //中序遍历
    public void inOrder (TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        count++;
        inOrder(root.right);
    }
    //后序遍历
    public void postOrder (TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
        count++;
    }
    public int size1 (TreeNode root) {
        //inOrder(root);
        int a = preOrder(root);
        return a;
    }
    public int preOrder (TreeNode root) {
        int count = 0;
        if (root != null) {
            //count++;
            count += preOrder(root.left);
            count += preOrder(root.right);
            return count + 1;
        }
        return count;
    }
    public int size (TreeNode root) {
        if (root == null) {
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }


    public int getLeafNodeCount1 (TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);
    }

    int leftCount = 0;
    public void getLeafNodeCount (TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leftCount++;
        } else {
            getLeafNodeCount(root.left);
            getLeafNodeCount(root.right);
        }
    }

    //获取某一层的节点个数
    public int getKLevelNodeCount (TreeNode root, int k) {
        if (root == null || k <= 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) +
                getKLevelNodeCount(root.right, k -1);
    }

    //获取二叉树的高度
    public int getHeight (TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight + 1: rightHeight + 1;

        //这样写的话  递归的次数太多了 重复计算了很多次
        /*return getHeight(root.left) > getHeight(root.right) ?
                getHeight(root.left) + 1 : getHeight(root.right) + 1;*/
    }

    //检测值为value的元素是否存在
    public TreeNode find (TreeNode root, char val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        TreeNode ch = find(root.left,val);
        if (ch != null) {
            return ch;
        }
        return find(root.right,val);
    }

    //判读是不是完全二叉树
    boolean isCompleteTree (TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur = queue.poll();
        while (cur != null) {
            queue.offer(cur.left);
            queue.offer(cur.right);
            cur = queue.poll();
        }
        while (!queue.isEmpty()) {
            if (queue.poll() != null) {
                return false;
            }
        }
        return true;
    }


}